import java.awt.Point;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;

public class Node {
	private Node parent;
	private Point pos;
	private char lMove;

	public Node(Node parent, Point pos, char from) {
		this.parent = parent;
		this.pos = pos;
		this.lMove = from;
	}

	/**
	 * find a path from the start position to the position of this node
	 * 
	 * @param start
	 * @param gState
	 * @return
	 */
	public static String findPath(GameState startState, GameState goalState) {
		LinkedList<Node> queue = new LinkedList<Node>();
		HashSet<Node> checkedNode = new HashSet<Node>();
		Node startNode = new Node(null, startState.playerPos, ' ');
		queue.addLast(startNode);
		checkedNode.add(startNode);
		String result = "";

		while (!queue.isEmpty()) {
			Node tempNode = queue.removeFirst();
			if (tempNode.pos.equals(goalState.playerBeforePush)) {
				result += goalState.lastMove;
				while (tempNode != null && tempNode.parent != null) {
					result = tempNode.lMove + result;
					tempNode = tempNode.parent;
				}
				return result;
			} else {
				for (Node child : tempNode.findChildren(startState)) {
					if (checkedNode.add(child)) {
						queue.addLast(child);
					}

				}
			}

		}
		return "no path";
	}

	/**
	 * find the children of the current node
	 * 
	 * @param gState
	 * @return
	 */
	public ArrayList<Node> findChildren(GameState gState) {
		char[][] tempMap = gState.generateMap();
		ArrayList<Node> result = new ArrayList<Node>();
		if (tempMap.length > pos.x + 1
				&& (tempMap[pos.x + 1][pos.y] == ' ' || tempMap[pos.x + 1][pos.y] == '.')) {
			result.add(new Node(this, new Point(pos.x + 1, pos.y), 'D'));
		}
		if (pos.x - 1 >= 0
				&& (tempMap[pos.x - 1][pos.y] == ' ' || tempMap[pos.x - 1][pos.y] == '.')) {
			result.add(new Node(this, new Point(pos.x - 1, pos.y), 'U'));
		}
		if (tempMap[pos.x].length > pos.y + 1
				&& (tempMap[pos.x][pos.y + 1] == ' ' || tempMap[pos.x][pos.y + 1] == '.')) {
			result.add(new Node(this, new Point(pos.x, pos.y + 1), 'R'));
		}
		if (pos.y - 1 >= 0
				&& (tempMap[pos.x][pos.y - 1] == ' ' || tempMap[pos.x][pos.y - 1] == '.')) {
			result.add(new Node(this, new Point(pos.x, pos.y - 1), 'L'));
		}

		return result;
	}

	public Point getPos() {
		return pos;
	}

	@Override
	public boolean equals(Object obj) {
		Node temp = (Node) obj;
		return pos.equals(temp.getPos());
	}
}
